public class QuickSort {
    public void quickSort(int []array){
        quick(array,0,array.length-1);
    }
    private void quick(int []array,int left,int right){//进行左右树的递归
        if(left>=right)return;
        int por=partition(array,left,right);
        quick(array,left,por-1);//左树
        quick(array,por+1,right);//右树
    }

    private int  partition(int []array,int start,int end){//将左右进行划分，并返回交换后的基准元素位置
        int i=start;
        while(start<end) {
            while (start<end&& array[end] >= array[i]) {//不加等号可能会使代码死循环，start和end始终不会相遇
                end--;
            }
            while (start<end&& array[start] <= array[i]) {
                start++;
            }
            swap(start, end, array);
        }
        swap(i,end,array);
        return end;
    }
    public void swap(int i,int j,int[]array){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
}
